package com.lry.basic.algorithm.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 简单无向图单源路径问题
 */
public class SingleSourcePath {
    private UndirectedGraph graph;

    private int source;//源点
    private int[] dfsPre;//上一个顶点的数组
    private int[] bfsPre;
    public SingleSourcePath(UndirectedGraph graph,int source){
        graph.validateVertex(source);
        this.source = source;
        this.graph = graph;
        dfsPre = new int[graph.vertexNum()];
        for(int i=0;i<dfsPre.length;i++){
            //-1表示顶点i还未访问
            dfsPre[i] = -1;
        }
        bfsPre = new int[graph.vertexNum()];
        for(int i=0;i<bfsPre.length;i++){
            //-1表示顶点i还未访问
            bfsPre[i] = -1;
        }
        dfs(source,source);
        bfs(source);
    }

    private void bfs(int v){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(v);
        while(!queue.isEmpty()){
            int w = queue.poll();
            for(int u:graph.adj(w)){
                if(bfsPre[u]==-1){
                    //代表w到u有边
                    bfsPre[u] = w;
                    queue.offer(u);
                }
            }
        }
    }

    /**
     * parent-> v 有路径
     * @param v
     * @param parent
     */
    private void dfs(int v,int parent){
        //parent到v有边
        dfsPre[v] = parent;
        for(int w:graph.adj(v)) {
            if(dfsPre[w]==-1){
                dfs(w,v);
            }
        }
    }

    public boolean dfsIsConnectedTo(int t){
        graph.validateVertex(t);
        return dfsPre[t]!=-1;
    }

    public boolean bfsIsConnectedTo(int t){
        graph.validateVertex(t);
        return bfsPre[t]!=-1;
    }

    /**
     * 返回s->t的路径
     * @param t
     * @return
     */
    public Iterable<Integer> dfsPath(int t){
        List<Integer> list = new ArrayList<>();
        if(!dfsIsConnectedTo(t)){return list;}

        while(t!=source){
            list.add(0,t);
            t = dfsPre[t];
        }
        list.add(0,source);
        return list;
    }

    public Iterable<Integer> bfsPath(int t){
        List<Integer> list = new ArrayList<>();
        if(!bfsIsConnectedTo(t)){return list;}

        while(t!=source){
            list.add(0,t);
            t = bfsPre[t];
        }
        list.add(0,source);
        return list;
    }


    public static void main(String[] args) {
        UndirectedGraph graph = new UndirectedGraph("graph.txt");
        System.out.println(graph);
        SingleSourcePath path = new SingleSourcePath(graph,0);
        System.out.println(path.dfsPath(1));
        System.out.println(path.dfsPath(2));
        System.out.println(path.dfsPath(3));
        System.out.println(path.dfsPath(4));
        System.out.println(path.dfsPath(5));
        System.out.println(path.dfsPath(6));
        System.out.println();
        System.out.println(path.bfsPath(1));
        System.out.println(path.bfsPath(2));
        System.out.println(path.bfsPath(3));
        System.out.println(path.bfsPath(4));
        System.out.println(path.bfsPath(5));
        System.out.println(path.bfsPath(6));
    }
}
